<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="kyVkV" id="kyVkV"><span data-lake-id="u837ea562" id="u837ea562">典型回答</span></h1>
  <p data-lake-id="u4b60d03f" id="u4b60d03f"><span data-lake-id="u8088bef5" id="u8088bef5">List主要有ArrayList、LinkedList与Vector几种实现。这三者都实现了List 接口，使用方式也很相似,主要区别在于因为实现方式的不同,所以对不同的操作具有不同的效率。</span></p>
  <p data-lake-id="ua9aadc76" id="ua9aadc76"><span data-lake-id="ufc0b55cd" id="ufc0b55cd">​</span><br></p>
  <p data-lake-id="u42c7a687" id="u42c7a687"><strong><span data-lake-id="u0472c85e" id="u0472c85e">ArrayList 是一个可改变大小的数组</span></strong><span data-lake-id="uda54e7ff" id="uda54e7ff">.当更多的元素加入到ArrayList中时,其大小将会动态地增长.内部的元素可以直接通过get与set方法进行访问,因为ArrayList本质上就是一个数组。</span></p>
  <p data-lake-id="u667e3c6f" id="u667e3c6f"><span data-lake-id="u9bf3d9b9" id="u9bf3d9b9">​</span><br></p>
  <p data-lake-id="u5ccfa5f2" id="u5ccfa5f2"><strong><span data-lake-id="uc422aa23" id="uc422aa23">LinkedList 是一个双向链表</span></strong><span data-lake-id="u18caa292" id="u18caa292">，在添加和删除元素时具有比ArrayList更好的性能，但在get与set方面弱于ArrayList。当然,这些对比都是指数据量很大或者操作很频繁的情况下的对比,如果数据和运算量很小,那么对比将失去意义。</span></p>
  <p data-lake-id="u7861e66e" id="u7861e66e"><span data-lake-id="u54b7d9aa" id="u54b7d9aa">​</span><br></p>
  <p data-lake-id="u32c7da28" id="u32c7da28"><strong><span data-lake-id="u8c55cedc" id="u8c55cedc">Vector 和ArrayList类似,但属于强同步类。</span></strong><span data-lake-id="u7c855b50" id="u7c855b50">如果你的程序本身是线程安全的(thread-safe,没有在多个线程之间共享同一个集合/对象),那么使用ArrayList是更好的选择。</span></p>
  <p data-lake-id="u0e8a350d" id="u0e8a350d"><span data-lake-id="u58628238" id="u58628238">​</span><br></p>
  <p data-lake-id="ua4469158" id="ua4469158"><span data-lake-id="ub87f1c7d" id="ub87f1c7d">Vector和ArrayList在更多元素添加进来时会请求更大的空间。Vector每次请求其大小的双倍空间，而ArrayList每次对size增长50%。</span></p>
  <p data-lake-id="ubf547d70" id="ubf547d70"><span data-lake-id="u1eb5498c" id="u1eb5498c">​</span><br></p>
  <p data-lake-id="u2f5bfb4e" id="u2f5bfb4e"><span data-lake-id="ua3e84d08" id="ua3e84d08">而 LinkedList 还实现了Queue和Deque接口,该接口比List提供了更多的方法,包括offer(),peek(),poll()等。</span></p>
  <p data-lake-id="udc27eb85" id="udc27eb85"><span data-lake-id="u7c7b73a2" id="u7c7b73a2">​</span><br></p>
  <p data-lake-id="uac588416" id="uac588416"><strong><span data-lake-id="uaa6cf56e" id="uaa6cf56e">注意: 默认情况下ArrayList的初始容量非常小,所以如果可以预估数据量的话,分配一个较大的初始值属于最佳实践,这样可以减少调整大小的开销。</span></strong></p>
  <h1 data-lake-id="eqwJ3" id="eqwJ3"><span data-lake-id="u09bb9185" id="u09bb9185">知识扩展</span></h1>
  <h2 data-lake-id="PWu9U" id="PWu9U"><span data-lake-id="ue3da5abf" id="ue3da5abf">ArrayList是如何扩容的？</span></h2>
  <p data-lake-id="u6a7e22a5" id="u6a7e22a5"><span data-lake-id="u4214d16c" id="u4214d16c">首先，我们要明白ArrayList是基于数组的，我们都知道，申请数组的时候，只能申请一个定长的数组，那么List是如何通过数组扩容的呢？ArrayList的扩容分为以下几步：</span></p>
  <ol list="ub849663f">
   <li fid="u51804d73" data-lake-id="u61054b82" id="u61054b82"><span data-lake-id="uf340b8f8" id="uf340b8f8">检查新增元素后是否会超过数组的容量，如果超过，则进行下一步扩容</span></li>
   <li fid="u51804d73" data-lake-id="u944608d6" id="u944608d6"><span data-lake-id="u23984220" id="u23984220">设置新的容量为老容量的1.5倍，最多不超过2^31-1 （Java 8中ArrayList的容量最大是Integer.MAX_VALUE - 8，即2^31-9。这是由于在Java 8中，ArrayList内部实现进行了一些改进，使用了一些数组复制的技巧来提高性能和内存利用率，而这些技巧需要额外的8个元素的空间来进行优化。）</span></li>
   <li fid="u51804d73" data-lake-id="u76ff1f19" id="u76ff1f19"><span data-lake-id="ub520e791" id="ub520e791">之后，申请一个容量为1.5倍的数组，并将老数组的元素复制到新数组中，扩容完成</span></li>
  </ol>
  <h2 data-lake-id="qNS3M" id="qNS3M"><span data-lake-id="uf49da6fa" id="uf49da6fa">如何利用List实现LRU？</span></h2>
  <p data-lake-id="u330f5505" id="u330f5505"><span data-lake-id="uf58a15eb" id="uf58a15eb">LRU，即最近最少使用策略，基于时空局部性原理（最近访问的，未来也会被访问），往往作为缓存淘汰的策略，如Redis和GuavaMap都使用了这种淘汰策略。</span></p>
  <p data-lake-id="u0e3653e6" id="u0e3653e6"><span data-lake-id="u58a083d4" id="u58a083d4">我们可以基于LinkedList来实现LRU，因为LinkedList基于双向链表，每个结点都会记录上一个和下一个的节点，具体实现方式如下：</span></p>
  <pre lang="java"><code>
public class LruListCache&lt;E&gt; {

    private final int maxSize;

    private final LinkedList&lt;E&gt; list = new LinkedList&lt;&gt;();

    public LruListCache(int maxSize) {
        this.maxSize = maxSize;
    }

    public void add(E e) {
        if (list.size() &lt; maxSize) {
            list.addFirst(e);
        } else {
            list.removeLast();
            list.addFirst(e);
        }
    }

    public E get(int index) {
        E e = list.get(index);
        list.remove(e);
        add(e);
        return e;
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

</code></pre>
  <h2 data-lake-id="FqfiS" id="FqfiS"><span data-lake-id="u5a385dca" id="u5a385dca">数组和链表的区别</span></h2>
 </body>
</html>